#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
using namespace std;


class Solution {
	string numToStr[10] = { " ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
public:

	void _letterCombinations(const string& digits, int i, vector<string>&strV, string str)
	{
		if (i == digits.size())
		{
			strV.push_back(str);
			return;
		}
		int num = digits[i] - '0';
		string s = numToStr[num];
		for (auto ch : s)
		{
			_letterCombinations(digits, i + 1, strV, str + ch);
		}
	}

	vector<string> letterCombinations(string digits)
	{
		vector<string> strV;
		if (digits.size() == 0)
			return strV;
		int i = 0;
		string str;

		_letterCombinations(digits, i, strV, str);
		return strV;
	}
};